/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:43
 */

// 300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 动态规划
        //时间复杂度为：O(N^2)
        //我们新创建一个dp数组来存放从原数组nums的0下标开始到该下标i ，包含nums[i]的最长递增子序列的长度
        int len=nums.length;
        int[] dp=new int[len];
        dp[0]=1;//从下标0到下标0，这一段的最长递增子序列就是0下标对应的值本身嘛，所以自然初始化为1啦

        //开始转移  填写dp数组
        for(int i=1;i<len;i++){
            //遍历i下标前面的下标值对应的nums数组的值（nums[j]），找到比nums[i]小的值,如果这个值对应的dp[j]的值大于dp[i],就让dp[i]=dp[j]+1
            // nums[j]<nums[i] -> dp[j]>=dp[i] ->  dp[i]=dp[j]+1

            for(int j=0;j<i;j++){
                //递增子序列，相等不属于递增：例如：实例3
                if(nums[j]<nums[i] && dp[j]>=dp[i]){
                    dp[i]=dp[j]+1;
                }
            }

            //如果它前面没有小于它的值，那么它就自己作为一个序列，所以dp[i]==1
            if(dp[i]==0){
                dp[i]=1;
            }
        }

        // 1  2  1  3  3  4
        //应该还需要遍历一遍dp数组，找到它存的值中的最大值
        int maxvalue=0;
        for(int i=0;i<len;i++){
            if(dp[i]>maxvalue){
                maxvalue=dp[i];
            }
        }


        return maxvalue;
    }
}
